---

deObjectTree.hpp

Go to the documentation of this file.

///////////////////////////////////////////////////////////////////////////////
/// @file deObjectTree.hpp
///
/// @brief [Adaptive] Binary Tree for objects
///
/// @author Assassin
///
/// This file is the intellectual property of Novus Delta, LLC.. Usage of the
/// contents of this file is subject to the Destiny3D Member License which
/// can be found at http://www.destiny3d.com.  Any other usage is prohibited.
///
/// This file is distributed "AS IS" without warranty of any kind.  Novus
/// Delta, LLC. does not guarantee the fitness of the contents of this file
/// for any particular purpose.
///
/// Copyright (C) 2001-2003 Novus Delta, LLC. All Rights Reserved.
///
/// <hr>
///                                 Change History
/// <hr>
///
/// @date Mar 2004
/// @author Assassin
/// @remarks Creation
///
///////////////////////////////////////////////////////////////////////////////

#ifndef DE_OBJECTTREE_HPP
#define DE_OBJECTTREE_HPP

#include "deGlobalTypes.hpp"
#include "deHash.hpp"
#include "deList.hpp"

class IdeSceneObject;
class IdeBoundingVolume;

class deObjectTree
{
public:
    deObjectTree();
    ~deObjectTree();

    deBoolean AddObject(IdeSceneObject* object);
    void RemoveObject(IdeSceneObject* object);
    deBoolean RepositionObject(IdeSceneObject* object);

    void IntersectionTest(IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);


private:
    /// a split in an ABT node, along an axis (0,1,2)=(x,y,z) at a certain percentage
    struct ABTSplit
    {
        long        Axis;
        deDouble    Percent;
    };
    /// a partition within the ABT.
    /// can have both child partitions and objects stored inside.
    /// non-leaf nodes can have faces if in limbo while compiling.
    struct ABTPartition
    {
        deAABB BBox;
        ABTSplit Split;
        ABTPartition* Parent;
        ABTPartition* Children[2]; // 0 = minside, 1 = maxside
        deTList<IdeSceneObject*> Objects;
    };
    /// information about a split - most important being the score.
    /// used only while partitioning a box, to score the various sampled splits
    struct ABTSplitStat
    {
        ABTSplit Split;
        dePlane Plane;
        long FrontBackDiff;
        long NumOn;
        deFloat Score;
    };

    typedef deTHashInt<ABTPartition*> ObjectHash_t;
    ABTPartition* m_Root;
    ObjectHash_t m_ObjectHash;
    int mObjectThreshold;
    int mDepthMax;

    ABTPartition* CreatePartition(ABTPartition* parent, int ChildNum, int AxisNum);
    deBoolean SplitPartition(ABTPartition* part, int Depth);
    void DestroyPartition(ABTPartition* part);
    void PrunePartition(ABTPartition* part, long Depth);
    deBoolean InsertObject(ABTPartition* part, IdeSceneObject* object, int Depth);
    deBoolean ExpandRoot(IdeSceneObject* outlier);
    void IntersectionHelper(ABTPartition* part, IdeBoundingVolume* BV, deTList<IdeSceneObject*>& outList);
};

#endif

---